// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的每个数字在每个组合中只能使用一次。

// 说明：
// 所有数字（包括目标数）都是正整数。
// 解集不能包含重复的组合。 

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
const combinationSum2 = function (candidates: number[], target: number) {
    const res: number[][] = []; // 结果数组
    const path: number[] = []; // 路径数组
    candidates.sort((a, b) => a - b); // 排序方便剪枝
    combinationSum2_DFS(candidates, target, res, path, 0);
    return res;
};

// 深度优先遍历回溯算法
function combinationSum2_DFS(candidates: number[], target: number,
    res: number[][], path: number[], begin: number) {
    if (target < 0) { // 递归出口1
        return;
    }
    if (target === 0) { // 递归出口2
        res.push(Array.from(path));
        return;
    }
    for (let i = begin; i < candidates.length; i++) {
        // 剪枝情况：当前选择元素与前一个元素相同，注意判断条件
        if (i > begin && candidates[i] === candidates[i - 1]) {
            continue;
        }
        path.push(candidates[i]);
        // 从当前选择点开始往下搜，而不允许往回搜索
        combinationSum2_DFS(candidates, target - candidates[i], res, path, i + 1);
        // 回溯算法部分5
        path.pop();
    }
}

// 这道题目是一道深度优先搜索结合回溯算法的问题，此外还考察了剪枝的应用
// 这道题的难点在于结果集的去重，例如[1,2,3]和[1,3,2]这种如何去重
// 我们需要先对原数组进行排序， 
// 在顺序搜索的过程中检测分支是否会出现重复结果
// 注意：这里的顺序不仅仅指原数组有序，还指按照一定顺序搜索路径结果
// 先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。
// 也就是说，剪枝发生在：同一层数值相同的结点第 2、3 ... 个结点，
// 因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，
// 同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1 个结点的子集。
// 这个剪枝的思想在于可以让同一层级，不出现相同的元素但是却允许了不同层级之间的重复
// 可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么答案中就不会再出现重复的数组。例如[1,2,2]
// 这也是不满足题目需求的，那么就用cur > begin 来避免这种情况，
// 你会发现重复解中的两个数是处在同一个层级上的，
// 而[1,2,2]中的两个数是处在不同层级上的
// 在一个for循环中，所有被遍历到的数都是属于一个层级的。
// 我们要让一个层级中，必须出现且只出现一个重复，那么就放过第一个出现重复的2，但不放过后面出现的2。
// 第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin。